package 实现数据结构.算法.异或;

/**
 * @Title
 * @Author zhengqiang.tan
 * @Date 2021/3/2 7:01 PM
 */
public class Xor {
    public static void main(String[] args) {

//        int[] arr = {2, 1, 4, 3, 4, 2, 3};
//        System.out.println(demo1(arr));
//        System.out.println(2 ^ 1);
//
//        System.out.println(demo2(8));
//        System.out.println(Integer.toBinaryString(8)); // 1000
//        System.out.println(Integer.toBinaryString(10));// 1010


        int[] arr2 = {5,4,5,6};
        swap2(arr2,1,0);

        System.out.println(arr2[0] + "--" + arr2[1]); // 4,3


//        System.out.println(Arrays.deepToString(arr2));

    }


    /**
     * 问题：
     * 一个数组中，只有数字 obj 出现了一次，其他数字都出现了两次。请查找出 obj，约束为 O(n) 的时间复杂度、O(1) 的空间复杂度。
     * <p>
     * 数组 a = [2,1,4,3,4,2,3] 中，则输出 1
     * <p>
     * 解决：异或有这样两个性质：第一，任何数异或自己为零；第二，任何数异或零，是它自己。
     * <p>
     * A ^ A = 0, A ^ 0 = A
     */
    public static int demo1(int[] arr) {
        if (arr == null || arr.length == 0) {
            new Exception("数组不能为空");
        }
        int result = arr[0];
        for (int i = 1, len = arr.length; i < len; i++) {
            result = result ^ arr[i];
        }
        return result;

    }

    /**
     * 判断一个整数 x，是否是 2 的整数次幂。
     * 解法就是，把 a 转换为二进制，看看 bin(a) 的形式是否为一个“1”和若干个“0”构成，
     *
     * @param x
     * @return
     */
    public static String demo2(int x) {
        if ((x & (x - 1)) == 0) {
            return "yes";
        } else {
            return "no";
        }
    }


    // ^是异或运算符，异或的规则是转换成二进制比较，相同为0，不同为1
    public static void swap2(int[] arr, int i, int j) {
        arr[i] = arr[i] ^ arr[j];
        arr[j] = arr[i] ^ arr[j];
        arr[i] = arr[i] ^ arr[j];
    }




}
